package goleetcode

import "math/bits"

func findProductsOfElements(queries [][]int64) []int {
	ans := make([]int, len(queries))
	for i, q := range queries {
		er := sumElement(int(q[1]) + 1)
		el := sumElement(int(q[0]))
		ans[i] = pow(2, er - el, int(q[2]))
	}
	return ans
}

func sumElement(k int) (res int) {
	var n, cnt1, sumI int
	for i := bits.Len(uint(k + 1)) - 1; i > 0 ; i-- {
		c := cnt1 << i + i << (i - 1)
		if c <= k {
			k -= c
			res += sumI << i + i * (i - 1) / 2 << (i - 1)
			sumI += i
			cnt1++
			n |= 1 << i
		}
	}
	if cnt1 <= k {
		k -= cnt1
		res += sumI
		n |= 1
	}
	for ; k > 0; k-- {
		res +=  bits.TrailingZeros(uint(n))
		n &= n - 1
	}
	return 
}

func pow(x, n, mod int) int {
	res := 1 % mod
	for ; n > 0; n /= 2 {
		if n%2 > 0 {
			res = res * x % mod
		}
		x = x * x % mod
	}
	return res
}